// type SudokuType = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

// class Sudoku {
//   static solve(board: string[][]) {
//     const line: SudokuType[] = Array.from({ length: 9 }, () => 0);
//     const column: SudokuType[] = Array.from({ length: 9 }, () => 0);
//     const block: SudokuType[][] = Array.from({ length: 3 }, () =>
//       Array.from({ length: 3 }, () => 0)
//     );
//     const spaces: [number, number][] = [];

//     // 翻转第i行第j列第digit位的值
//     function flip(i: number, j: number, digit: number) {
//       // 创建一个掩码，用于翻转第digit位的值
//       const mask = 1 << digit;
//       // 翻转第i行的第digit位的值
//       line[i] ^= mask;
//       // 翻转第j列的第digit位的值
//       column[j] ^= mask;
//       // 翻转第i行第j列所在的3x3宫格的第digit位的值
//       block[Math.floor(i / 3)][Math.floor(j / 3)] ^= mask;
//     }

//     for (let i = 0; i < 9; i++) {
//       for (let j = 0; j < 9; j++) {
//         if (board[i][j] === ".") {
//           spaces.push([i, j]);
//         } else {
//           const digit = parseInt(board[i][j]) - 1;
//           flip(i, j, digit);
//         }
//       }
//     }

//     // 深度优先搜索函数
//     function dfs(pos: number): boolean {
//       // 如果当前位置等于空格数组的长度，说明已经填满，返回true
//       if (pos === spaces.length) {
//         return true;
//       }
//       // 获取当前位置的行和列
//       const [i, j] = spaces[pos];
//       // 计算当前位置的掩码，即当前位置可以填的数字
//       let mask =
//         0x1ff & // 将掩码限制在9位
//         ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]); // 将行、列、块中的数字从掩码中去除
//       // 当掩码大于0时，说明还有数字可以填
//       while (mask > 0) {
//         // 获取掩码中最低位的数字
//         const digit = Math.log2(mask & -mask);
//         // 将数字填入当前位置
//         flip(i, j, digit);
//         board[i][j] = `${digit + 1}`; // 将数字转换为字符串
//         // 递归调用dfs函数，如果返回true，说明已经填满，返回true
//         if (dfs(pos + 1)) {
//           return true;
//         }
//         // 如果没有填满，将数字从当前位置去除
//         flip(i, j, digit);
//         mask &= mask - 1; // 将掩码中最低位的数字去除
//       }
//       // 如果没有数字可以填，返回false
//       return false;
//     }
//     dfs(0);
//   }
// }

// export default Sudoku;

type SudokuItem = "." | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
// type SudokuVal = Omit<SudokuItem, ".">;

function getAreaNumber(row: number, col: number) {
  return Math.floor(row / 3) * 3 + Math.floor(col / 3);
}

export function solveSudoku(board: SudokuItem[][]) {
  const rows: boolean[][] = new Array(9)
    .fill(0)
    .map((_) => new Array(10).fill(false));
  const cols: boolean[][] = new Array(9)
    .fill(0)
    .map((_) => new Array(10).fill(false));
  const areas: boolean[][] = new Array(9)
    .fill(0)
    .map((_) => new Array(10).fill(false));
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const val = board[i][j];
      if (val !== ".") {
        rows[i][val] = true;
        cols[j][val] = true;
        areas[getAreaNumber(i, j)][val] = true;
      }
    }
  }

  function dfs(curBoard: SudokuItem[][], index: number) {
    let finish = false;
    if (index === 81) {
      finish = true;
      return true;
    }
    const row = Math.floor(index / 9);
    const col = index % 9;
    const val = curBoard[row][col];
    if (val !== ".") {
      dfs(curBoard, index + 1);
    } else {
      for (let n = 1; n <= 9; n++) {
        let tempRow = rows[row][n],
          tempCol = cols[col][n],
          tempArea = areas[getAreaNumber(row, col)][n];

        if (!tempRow && !tempCol && !tempArea) {
          rows[row][n] = true;
          cols[col][n] = true;
          areas[getAreaNumber(row, col)][n] = true;
          curBoard[row][col] = n.toString() as SudokuItem;
          dfs(curBoard, index + 1);
          if (finish) {
            return;
          }
          curBoard[row][col] = ".";
          rows[row][n] = tempRow;
          cols[col][n] = tempCol;
          areas[getAreaNumber(row, col)][n] = tempArea;
        }
      }
    }
  }

  dfs(board, 0);
}
